﻿/*
 * This file is part of MonoSettlers.
 *
 * Copyright (C) 2010-2011 Christoph Husse
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Affero General Public License as
 *  published by the Free Software Foundation, either version 3 of the
 *  License, or (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Affero General Public License for more details.
 *
 *  You should have received a copy of the GNU Affero General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Authors: 
 *      # Christoph Husse
 * 
 * Also checkout our homepage: http://opensettlers.codeplex.com/
 */
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Serialization;
using System.ComponentModel;
using System.Collections.ObjectModel;

namespace MonoSettlers
{
    [Flags]
    public enum MapPolicy : int
    {
        None = 0,
        AllowDuplicates = 1,
        DefaultForNonExisting = 2,
        CreateNonExisting = 4,
        SortManually = 8,
    }

    public class ReadonlySettableList<TValue> : IList<TValue>
    {
        private IList<TValue> m_List;

        public ReadonlySettableList(IList<TValue> inList)
        {
            m_List = inList;
        }

        public void Add(TValue item)
        {
            throw new InvalidOperationException("The collection is readonly.");
        }

        public void Clear()
        {
            throw new InvalidOperationException("The collection is readonly.");
        }

        public bool Contains(TValue item)
        {
            return m_List.Contains(item);
        }

        public void CopyTo(TValue[] array, int arrayIndex)
        {
            m_List.CopyTo(array, arrayIndex);
        }

        public int Count
        {
            get { return m_List.Count; }
        }

        public bool IsReadOnly
        {
            get { return true; }
        }

        public bool Remove(TValue item)
        {
            throw new InvalidOperationException("The collection is readonly.");
        }

        public IEnumerator<TValue> GetEnumerator()
        {
            return m_List.GetEnumerator();
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return m_List.GetEnumerator();
        }

        public int IndexOf(TValue item)
        {
            return m_List.IndexOf(item);
        }

        public void Insert(int index, TValue item)
        {
            throw new InvalidOperationException("The collection is readonly.");
        }

        public void RemoveAt(int index)
        {
            throw new InvalidOperationException("The collection is readonly.");
        }

        public TValue this[int index]
        {
            get
            {
                return m_List[index];
            }
            set
            {
                m_List[index] = value;
            }
        }
    }

    public class MapTest
    {
        public static void Run()
        {
            UniqueMap<Int32, Int32> test = new UniqueMap<int, int>();
            Random rnd = new Random(0);

            for (int i = 0; i < 30; i++)
            {
                test.Add(rnd.Next(), i);
            }

            for (int i = 1; i < 30; i++)
            {
                if (test.Keys.ElementAt(i - 1) > test.Keys.ElementAt(i))
                    throw new ApplicationException("MapTest failed!");
            }

            for (int i = 0; i < 30; i++)
            {
                if (test[test.Keys.ElementAt(i)] != test.Values[i])
                    throw new ApplicationException("MapTest failed!");
            }
        }
    }

    /// <summary>
    /// A more flexible solution than the original SortedList provided by Microsoft.
    /// </summary>
    /// <typeparam name="TKey"></typeparam>
    /// <typeparam name="TValue"></typeparam>
    [Serializable]
    public class Map<TKey, TValue> : IDictionary<TKey, TValue>, ICollection<KeyValuePair<TKey, TValue>>, IEnumerable<KeyValuePair<TKey, TValue>>
    {
        static Map()
        {
            MapTest.Run();
        }

        private BindingList<TKey> m_Keys = new BindingList<TKey>();
        private BindingList<TValue> m_Values = new BindingList<TValue>();
        [NonSerialized]
        private int modID = 0;
        private MapPolicy m_Policy;
        private IComparer<TKey> m_Comparator;

        public MapPolicy Policy { get { return m_Policy; } }

        public Map(MapPolicy inPolicy)
        {
            m_Policy = inPolicy;
            m_Comparator = Comparer<TKey>.Default;
        }

        public Map(MapPolicy inPolicy, Func<TKey, TKey, int> inComparator)
        {
            m_Policy = inPolicy;
            m_Comparator = new FuncComparer(inComparator);
        }

        [ Serializable]
        private class FuncComparer : IComparer<TKey>
        {
            public Func<TKey, TKey, int> Comparator { get; set; }

            public FuncComparer(Func<TKey, TKey, int> inComparator)
            {
                Comparator = inComparator;
            }

            public int Compare(TKey x, TKey y)
            {
                return Comparator(x, y);
            }
        }

        public Map(MapPolicy inPolicy, IComparer<TKey> inComparator)
        {
            m_Policy = inPolicy;
            m_Comparator = inComparator;
        }

        public void InitializeUnsorted(IEnumerable<TKey> inKeys, IEnumerable<TValue> inValues)
        {
            InitializeUnsorted(inKeys.AsQueryable(), inValues.AsQueryable());
        }

        public void InitializeUnsorted(IEnumerable<KeyValuePair<TKey, TValue>> inPairs)
        {
            InitializeSortedUnsafe(inPairs.OrderBy(e => e.Key, m_Comparator));
        }

        /// <summary>
        /// Only use this method for high-performance cases, since initial sorting is not enforced. This may lead
        /// to a corrupted map if you don't know exactly that the given pairs are already sorted!
        /// </summary>
        /// <param name="inPairs"></param>
        public void InitializeSortedUnsafe(IEnumerable<KeyValuePair<TKey, TValue>> inPairs)
        {
            m_Keys = new BindingList<TKey>(inPairs.Select(e => e.Key).ToList());
            m_Values = new BindingList<TValue>(inPairs.Select(e => e.Value).ToList());
        }

        public void Add(TKey key, TValue value)
        {
            Add(new KeyValuePair<TKey, TValue>(key, value));
        }

        public bool ContainsKey(TKey key)
        {
            return m_Keys.BinarySearch(key, m_Comparator) >= 0;
        }

        public BindingList<TKey> GetKeyBinding()
        {
            return m_Keys;
        }

        public BindingList<TValue> GetValueBinding()
        {
            return m_Values;
        }

        public ICollection<TKey> Keys
        {
            get { return new ReadOnlyCollection<TKey>(m_Keys); }
        }

        public bool Remove(TKey key)
        {
            int pos = m_Keys.BinarySearch(key, m_Comparator);

            if (pos < 0)
                return false;

            m_Keys.RemoveAt(pos);
            m_Values.RemoveAt(pos);

            modID++;

            return true;
        }

        public bool TryGetValue(TKey key, out TValue value)
        {
            int pos = m_Keys.BinarySearch(key, m_Comparator);

            value = default(TValue);

            if (pos < 0)
                return false;

            value = m_Values[pos];

            return true;
        }

        public IList<TValue> Values
        {
            get { return new ReadonlySettableList<TValue>(m_Values); }
        }

        ICollection<TValue> System.Collections.Generic.IDictionary<TKey, TValue>.Values
        {
            get { return new ReadOnlyCollection<TValue>(m_Values); }
        }

        public TValue this[TKey key]
        {
            get
            {
                int pos = m_Keys.BinarySearch(key, m_Comparator);

                if (pos < 0)
                {
                    if ((Policy & MapPolicy.DefaultForNonExisting) == 0)
                        throw new KeyNotFoundException();

                    return default(TValue);
                }

                return m_Values[pos];
            }
            set
            {
                int pos = m_Keys.BinarySearch(key, m_Comparator);

                if (pos < 0)
                {
                    if ((Policy & MapPolicy.CreateNonExisting) == 0)
                        throw new KeyNotFoundException();

                    Add(key, value);

                    return;
                }

                m_Values[pos] = value;
            }
        }

        public void Add(KeyValuePair<TKey, TValue> item)
        {
            int pos = m_Keys.BinarySearch(item.Key, m_Comparator);

            if (pos < 0)
            {
                // unique insert
                pos = -pos - 1;
            }
            else
            {
                // duplicate insert
                if ((Policy & MapPolicy.AllowDuplicates) == 0)
                    throw new NotSupportedException("The map already contains a key with this value and duplicates are not permitted.");
            }

            m_Keys.Insert(pos, item.Key);
            m_Values.Insert(pos, item.Value);
            modID++;
        }

        public void Clear()
        {
            m_Keys.Clear();
            m_Values.Clear();
            modID++;
        }

        public bool Contains(KeyValuePair<TKey, TValue> item)
        {
            TValue value;

            if (!TryGetValue(item.Key, out value))
                return false;

            return item.Value.Equals(value);
        }

        public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
        {
            if (Count + arrayIndex > array.Length)
                throw new IndexOutOfRangeException();

            for (int i = 0, x = arrayIndex, c = Count; i < c; i++, x++)
            {
                array[x] = new KeyValuePair<TKey, TValue>(m_Keys[i], m_Values[i]);
            }
        }

        public int Count
        {
            get { return m_Keys.Count; }
        }

        public bool IsReadOnly
        {
            get { return false; }
        }

        public bool Remove(KeyValuePair<TKey, TValue> item)
        {
            int pos = m_Keys.BinarySearch(item.Key, m_Comparator);

            if (pos < 0)
                return false;

            if (m_Values[pos].Equals(item.Value))
                return false;

            m_Keys.RemoveAt(pos);
            m_Values.RemoveAt(pos);
            modID++;

            return true;
        }

        public IEnumerable<KeyValuePair<TKey, TValue>> Search(TKey inPattern, IComparer<TKey> inComparer)
        {
            int offset = m_Keys.BinarySearch(inPattern, inComparer);
            List<KeyValuePair<TKey, TValue>> result = new List<KeyValuePair<TKey, TValue>>();

            if (offset < 0)
                return result;

            for (int i = offset; i >= 0; i--)
            {
                if (inComparer.Compare(inPattern, m_Keys[i]) != 0)
                    break;

                result.Add(new KeyValuePair<TKey, TValue>(m_Keys[i], m_Values[i]));
            }

            for (int i = offset + 1, count = m_Keys.Count; i < count; i++)
            {
                if (inComparer.Compare(inPattern, m_Keys[i]) != 0)
                    break;

                result.Add(new KeyValuePair<TKey, TValue>(m_Keys[i], m_Values[i]));
            }

            return result;
        }

        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            return new KeyValuePairEnum(this);
        }

        private class KeyValuePairEnum : IEnumerator<KeyValuePair<TKey, TValue>>
        {
            private Map<TKey, TValue> map;
            private int modID;
            private int index = -1;

            public KeyValuePairEnum(Map<TKey, TValue> inMap)
            {
                map = inMap;
                modID = inMap.modID;
            }

            private void CheckModification()
            {
                if (modID != map.modID)
                    throw new InvalidOperationException("Collection has been modified during enumeration.");
            }

            public KeyValuePair<TKey, TValue> Current
            {
                get
                {
                    CheckModification();

                    return new KeyValuePair<TKey, TValue>(map.m_Keys[index], map.m_Values[index]);
                }
            }

            public void Dispose()
            {
                map = null;
                index = -1;
            }

            object System.Collections.IEnumerator.Current
            {
                get { return this.Current; }
            }

            public bool MoveNext()
            {
                CheckModification();

                if (index + 1 >= map.Count)
                    return false;

                index++;

                return true;
            }

            public void Reset()
            {
                CheckModification();

                index = -1;
            }
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }
    }

    [ Serializable]
    public class UniqueMap<TKey, TValue> : Map<TKey, TValue>
    {
        public UniqueMap()
            : base(MapPolicy.None)
        {
        }
    }

    [ Serializable]
    public class UniqueKeyMap<TKey> : UniqueMap<TKey, Object> { }

    [ Serializable]
    public class CollectionMap<TKey, TValue> : Map<TKey, TValue>
    {
        public CollectionMap()
            : base(MapPolicy.AllowDuplicates)
        {
        }
    }

    [ Serializable]
    public class AutoCollectionMap<TKey, TValue> : Map<TKey, TValue>
    {
        public AutoCollectionMap()
            : base(MapPolicy.AllowDuplicates | MapPolicy.DefaultForNonExisting | MapPolicy.CreateNonExisting)
        {
        }
    }

    [ Serializable]
    public class AutoUniqueMap<TKey, TValue> : Map<TKey, TValue>
    {
        public AutoUniqueMap()
            : base(MapPolicy.AllowDuplicates | MapPolicy.DefaultForNonExisting | MapPolicy.CreateNonExisting)
        {
        }
    }
}
